|
:''See simplex algorithm for Dantzig's algorithm for the problem of linear optimization.'' The Nelder–Mead method or downhill simplex method or amoeba method is a commonly applied numerical method used to find the minimum or maximum of an objective function in a many-dimensional space. It is applied to nonlinear optimization problems for which derivatives may not be known. However, the Nelder–Mead technique is a heuristic search method that can converge to non-stationary points〔 * * (algorithm summary online). 〕 on problems that can be solved by alternative methods.〔 *Yu, Wen Ci. 1979. “Positive basis and a class of direct search techniques”. ''Scientia Sinica'' (Kexue'' ): 53—68. *Yu, Wen Ci. 1979. “The convergent property of the simplex evolutionary technique”. ''Scientia Sinica'' (Kexue'' ): 69–77. * * 〕 The Nelder–Mead technique was proposed by John Nelder & Roger Mead (1965).〔 〕 == Overview == The method uses the concept of a simplex, which is a special polytope of ''n'' + 1 vertices in ''n'' dimensions. Examples of simplices include a line segment on a line, a triangle on a plane, a tetrahedron in three-dimensional space and so forth. The method approximates a local optimum of a problem with ''n'' variables when the objective function varies smoothly and is unimodal. For example, a suspension bridge engineer has to choose how thick each strut, cable, and pier must be. These elements are interdependent, but it is not easy to visualize the impact of changing any specific element. Simulation of such complicated structures is often extremely computationally expensive to run, possibly taking upwards of hours per execution. An engineer may therefore prefer the Nelder-Mead method as it requires fewer evaluations per iteration than other optimization methods. Nelder–Mead in ''n'' dimensions maintains a set of ''n+1'' test points arranged as a simplex. It then extrapolates the behavior of the objective function measured at each test point, in order to find a new test point and to replace one of the old test points with the new one, and so the technique progresses. The simplest approach is to replace the worst point with a point reflected through the centroid of the remaining ''n'' points. If this point is better than the best current point, then we can try stretching exponentially out along this line. On the other hand, if this new point isn't much better than the previous value, then we are stepping across a valley, so we shrink the simplex towards a better point. An intuitive explanation of the algorithm is presented in 〔 * 〕
Unlike modern optimization methods, the Nelder–Mead heuristic can converge to a non-stationary point unless the problem satisfies stronger conditions than are necessary for modern methods.〔 Modern improvements over the Nelder–Mead heuristic have been known since 1979.〔 Many variations exist depending on the actual nature of the problem being solved. A common variant uses a constant-size, small simplex that roughly follows the gradient direction (which gives steepest descent). Visualize a small triangle on an elevation map flip-flopping its way down a valley to a local bottom. This method is also known as the Flexible Polyhedron Method. This, however, tends to perform poorly against the method described in this article because it makes small, unnecessary steps in areas of little interest. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Nelder–Mead method」の詳細全文を読む スポンサード リンク
|